package 五排序;

import java.util.Arrays;

/**
 * @Author XuZhuHong
 * @CreateTime 2021/9/27 10:09
 */
public class HeapSort {
    private static int[] array;


    public static void main(String[] args) {
        //要求将数组进行升序排序
        array = new int[]{4, 6, 8, 5, 9};
        //i的值是完全二叉树的子节点的个数 从最后一个子节点依次网上排序执行
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            adjustHeap(array, i, array.length);
        }
        System.out.println(Arrays.toString(array));

        //递归把值往上移动
        for (int i = (array.length - 1); i >= 0; i--) {
            //把第一个值放到最后
            array[0] = array[0] + array[i];
            array[i] = array[0] - array[i];
            array[0] = array[0] - array[i];
            adjustHeap(array, 0, i);
        }

        System.out.println(Arrays.toString(array));
//        infixOrder();
    }

    private static void adjustHeap(int[] arr, int i, int length) {
        //arr[i]为父节点   a[k]为他的右子节点
        //定位到左子节点
        int k = i * 2 + 2;
        //表示k 已经发生了下标越界
        if (k >= length) {
            return;
        }
        //如果当前的这个节点的左子结点大  那么就调交换位置
        if (arr[k] < arr[k - 1]) {
            //值交换
            arr[k] = arr[k] + arr[k - 1];
            arr[k - 1] = arr[k] - arr[k - 1];
            arr[k] = arr[k] - arr[k - 1];
        }

        //如果a【i】比他的右节点小 那么就交换值
        if (arr[i] < arr[k]) {
            arr[i] = arr[i] + arr[k];
            arr[k] = arr[i] - arr[k];
            arr[i] = arr[i] - arr[k];
        }
    }

    public static void infixOrder() {
        infixOrder(0);
    }

    //中序遍历
    public static void infixOrder(int index) {
        if (array == null || array.length < 0) {
            System.out.println("空数组无法遍历");
            return;
        }
        //左遍历
        if ((2 * index) + 1 < array.length) {
            infixOrder((2 * index) + 1);
        }
        System.out.println(array[index]);
        //右遍历
        if ((2 * index) + 2 < array.length) {
            infixOrder((2 * index) + 2);
        }
    }

}
